1. Field of the Invention
This invention relates to the field of data processing systems. More particularly, this invention relates to the field of accessing data within a cache.
2. Description of the Prior Art
Caches within data processors can store large amounts of data. Accessing data within caches can be quite a complicated procedure requiring addresses of a relatively large size. Manipulation of such addresses can therefore require significant amounts of power and time. Caches have been organised in a number of ways in order to reduce power and time overheads involved in accessing storage locations within the caches.
One popular way of configuring a cache is the so-called ‘set associative’ cache. A 16 Kbyte set associative cache is shown in FIG. 1. The cache shown is such a 4-way set associative cache 10 having 4 ways 11, 12, 13, 14 each containing a number of cache lines 20. A data value (in the following examples, a word) associated with a particular address 35 can be stored in a particular cache line of any of the 4 ways (i.e. each set has 4 cache lines, as illustrated generally by reference numeral 22). Each way stores 4 Kbytes (16 Kbyte cache/4 ways). If each cache line stores eight 32-bit words then there are 32 bytes/cache line (8 words×4 bytes/word) and 128 cache lines in each way ((4 Kbytes/way)/(32 bytes/cache line)). Hence, in this illustrative example, the total number of sets would be equal to 128, i.e. ‘M’ in the figure would be 127.
In order to address data stored in this sort of a cache an address 35 comprising a SET or index portion 37, which indicates which of the sets or lines the address is referring to and a TAG portion 36 indicating which of the four ways it is in is used. Such an address identifies a cache line and a cache way. The line being identified by the set and a comparison and match of TAGs stored in 4 TAG RAMs 25 with the TAGs in the corresponding set of the 4 caches 10 indicating the way. In reality more than one data word may be stored in a cache line within a cache way and thus, the address may contain further information.
When accessing data stored in a cache organised in this way, any virtual address produced by a programming model will need to be converted to a physical address. This can slow the procedure, as the program will produce the virtual address early, but the data cannot be accessed until it is converted to a physical address.
A known way of converting a virtual address to a physical address is by the use of a translation lookaside buffer or TLB. FIG. 2 shows a known way of accessing data during which a virtual address is converted to a physical address, the physical address then being used to access the data. In this Figure a table lookaside buffer (TLB) 30, receives a virtual address from a programmer's model and converts it to a physical address. The physical address 35 comprises a tag portion 36 and an index portion 37. The index portion is used to indicate which set within the cache ways the address refers to. Thus, a corresponding line within the plurality of cache tag directories 40 is selected using the index portion of address 35. The tag portion 36 of address 35 is then compared in comparator 60 with the four tags stored in each of the four cache tag directories that correspond to the four ways of the cache. When a comparison gives a match this indicates the cache way storing the data item and this data item can then be accessed from cache 50 using multiplexer 70.
This is one way in which data identified by a virtual address can be accessed. The initial step in this procedure is conversion of the virtual address to a physical address using a table lookaside buffer. This is not a fast step and thus, having this as the first step in the procedure considerably slows the critical path. An alternative to this is shown in FIG. 3. This system is referred to as a virtually indexed/physically tagged cache system. In this example the data access is performed using the virtual index to select which set (or line) the tag will be stored in. Thus, as soon as the virtual address is available this step can be performed in parallel with the conversion of the virtual address to a physical address using the TLB 30. Once the physical tag has been produced by the TLB 30 this is compared with the four tags selected from the cache tag directory by the index. When a match is found then this is used to access the data from the cache 50.
This is faster than the data access shown in FIG. 2. However, tags can be relatively long pieces of data, for example a memory system which has a 32 K 4-way set-associative cache structure (consisting of 64 byte cache line size), would have tags of 19 bits (for a processor with 32-bit addresses). Thus, the comparison stage can be slow.
Furthermore, this process requires the accessing of multiple RAMs i.e. multiple cache tag directories and cache data arrays (RAMs) are accessed during the procedure and power consumption is therefore high.